package lib

//link to 918
func init() {
	Probs = append(Probs, Problem{
		Num:         503,
		Discription: "循环数组中每一个元素的下一个最大元素",
		Level:       2,
		Labels: map[string]int{
			"单调栈": 1,
			"循环数组": 1,
		},
	})
}

func NextGreaterElements(nums []int) []int {
	s := make([]int, 0)
	nextBigger := make([]int, len(nums))

	//维护一个单调递减的栈（记录索引）
	for i := range nums {
		//每当有元素比栈顶大了，就出栈，同时记录其下一个右侧元素的ID
		for len(s) > 0 && nums[s[len(s)-1]] < nums[i] {
			nextBigger[s[len(s)-1]] = nums[i]
			s = s[:len(s)-1]
		}
		s = append(s, i)
	}

	//第一轮遍历后栈中剩下的元素，是正常数组视角下右侧没有更大的元素的，需要循环数组来找下一个更大的元素
	//还是单调栈，但是不需要进栈了，单纯判断是否比栈顶大即可
	i := 0
	for len(s) > 0 && i < len(nums) {
		//循环到自己，表示过了一圈了都没找到最大元素
		if i == s[0] {
			s = s[1:]
			nextBigger[i] = -1
		}

		for len(s) > 0 && nums[s[len(s)-1]] < nums[i] {
			nextBigger[s[len(s)-1]] = nums[i]
			s = s[:len(s)-1]
		}

		i++
	}

	return nextBigger
}